GATE CSE 2020
Q31.
Let G=(V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u,v)\in V \times V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph isQ32.
Consider a graph G=(V,E), where V=\{v_1,v_2,...,v_{100}\}, E=\{(v_i,v_j)|1\leq i \lt j\leq 100\}, and weight of the edge (v_i,v_j)\; is \; |i-j|. The weight of minimum spanning tree of G is _________Q33.
Consider the following language. L={x \in \{a,b\}^*| number of a's in x divisible by 2 but not divisible by 3} The minimum number of states in DFA that accepts L is _______Q34.
Consider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200000, respectively. If R3=\frac{R1}{R2}, what is the value stored in R3?Q35.
Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?Q36.
A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a 4-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are 8 distinct I-type opcodes, then the maximum number of distinct R-type opcodes is _______.Q37.
Consider the following data path diagram. Consider an instruction: R0\leftarrow R1+R2. The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r and w indicate read and write operations, respectively. 1. \; R2_r,TEMP1_r,ALU_{add},TEMP2_w 2. \; R1_r,TEMP1_w 3. \; PC_r,MAR_w,MEM_r 4. \; TEMP2_r,R0_w 5. \; MDR_r,IR_w Which one of the following is the correct order of execution of the above steps?Q38.
Consider the following grammar. S\rightarrow aSB|d B\rightarrow b The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is___________.Q39.
Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to 2 decimal places) is________.Q40.
For n\gt2, let a \in \{0,1\}^n be a non-zero vector. Suppose that x is chosen uniformly at random from \{0,1\}^n. Then, the probability that \sum_{i=1}^{n}a_ix_i is an odd number is______